//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 
//
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
// 
//
// 示例 2： 
//
// 
//输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//     注意，你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 
//输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 300 
// 1 <= wordDict.length <= 1000 
// 1 <= wordDict[i].length <= 20 
// s 和 wordDict[i] 仅有小写英文字母组成 
// wordDict 中的所有字符串 互不相同 
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 👍 1568 👎 0

package leetcode.editor.cn;

import java.util.*;

class WordBreak {
    public static void main(String[] args) {
        Solution solution = new WordBreak().new Solution();
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        solution.wordBreak("leetcode", list);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public boolean wordBreak(String s, List<String> wordDict) {
            // dp数组表示i的背包容量是否可以拆分出单词，dp[i]表示是否
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;

            for (int i = 1; i <= s.length(); i++) {  // 先遍历背包
                for (int j = 0; j < i; j++) {
                    String str = s.substring(j, i);
                    if (wordDict.contains(str) && dp[j] != false) { // 当以前的串可以拆分，并且包含此单词
                        dp[i] = true;
                    }
                }
            }

            return dp[s.length()];
        }*/

        /**
         * 回溯法
         *
         * @param s
         * @param wordDict
         * @return
         */
        public boolean wordBreak(String s, List<String> wordDict) {
            set = new HashSet<>(wordDict);
            memo = new int[s.length()];
            return traversal(s, 0);
        }

        private Set<String> set;
        private int[] memo; // 用来标记startIndex是否被选择过（-1表示从startIndex开始选择不满足）

        public boolean traversal(String s, int startIndex) {
            // 是否选择到边界
            if (startIndex >= s.length()) {
                return true;
            }

            // 如果被选择过，直接返回结果
            if (memo[startIndex] == -1) {
                return false;
            }

            for (int i = startIndex; i < s.length(); i++) {
                String str = s.substring(startIndex, i + 1);
                // 如果单词在字典中，且递归后边的都返回true，则此时字符串满足
                if (set.contains(str) && traversal(s, i + 1)) {
                    return true;
                }
            }

            // 标记
            memo[startIndex] = -1;
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
